Nonlinearity of Boolean functions: an algorithmic approach based on multivariate polynomials

摘要

We compute the nonlinearity of Boolean functions with Groebner basistechniques, providing two algorithms: one over the binary field and the otherover the rationals. We also estimate their complexity. Then we show how toimprove our rational algorithm, arriving at a worst-case complexity of$O(n2^n)$ operations over the integers, that is, sums and doublings. This way,with a different approach, we reach the same complexity of establishedalgorithms, such as those based on the fast Walsh transform.